ass Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for(int dest = -1,cur=0;cur!=nums.size();cur++){
            if(nums[cur]){
                swap(nums[cur],nums[++dest]);
            }
        }
        // int n= nums.size(),left = 0,right = 0;
        // while(right<n){
        //     if(nums[right]!=0){
        //         swap(nums[left],nums[right]);
        //         left++;
        //     }
        //     right++;
        // }
    }
};

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur=0,dest=-1,n=arr.size();
        //1. 找到最后一个 复写 的数
        while(cur<n)
        {
            if(arr[cur]) dest++;
            else dest+=2;

            if(dest>=n-1) break;
            cur++;
        }
        //2. 处理边界
        if(dest==n)
        {
            arr[dest-1]=0;
            dest-=2;
            cur--;
        }
        //3. 从后往前 复写
        while(cur>=0)
        {
            if(arr[cur])
                arr[dest--]=arr[cur--];
            else
            {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            }
        }
    }
};

class Solution {
public:
    // int GetNext(int n)
    // {
    //     int ret = 0;
    //     while(n)
    //     {
    //         ret += (n%10)*(n%10);
    //         n/=10;
    //     }
    //     return ret;
    // }

    int bitSum(int n)
    {
        int sum=0;            
        while(n)
        {
            sum+= (n%10)*(n%10);
            n/=10;
        }
        return sum;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = bitSum(bitSum(n));
        while(slow!=fast)
        {
            slow = bitSum(slow);
            fast = bitSum(bitSum(fast));
        }
        return slow==1;
        // int p=n;
        // int q=n;
        // do{
        //     p = GetNext(p);
        //     q = GetNext(GetNext(q));
        // }while(p!=q && q!=1);
        // return q==1;
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right=height.size()-1,ret=0;
        while(left<right)
        {
            int v = min(height[left],height[right]) * (right-left);
            if(v>ret) ret = v;
            if(height[left]<=height[right]) left++;
            else right--;
        }
        return ret;

    //     int left = 0,right = height.size()-1,ret = 0;
    //     ret = min(height[left],height[right])*(right-left);
    //     while(left<right){
    //         if(height[left]<=height[right])
    //         {
    //             left++;
    //         }
    //         else
    //         {
    //             right--;
    //         }
    //         if(ret<min(height[left],height[right])*(right-left))
    //         ret = min(height[left],height[right])*(right-left);
    //     }
    //     return ret;
    // }
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1. 优化
        sort(nums.begin(),nums.end());
        //2. 双指针
        int ret=0,n=nums.size();
        for(int i=n-1;i>=2;i--)//先固定最大的数
        {
            //利用双指针快速统计符合要求的三元组的个数
            int left=0,right=i-1;
            while(left<right)
            {
                if(nums[left]+nums[right]>nums[i]) 
                {
                    ret+=right-left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int  left=0,right=nums.size()-1;
        while(left<right)
        {
            if(nums[left]+nums[right]>target) right--;
            else if(nums[left]+nums[right]<target) left++;
            else return {nums[left],nums[right]};
        }
        return {-1,-1};
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        //1. 排序
        sort(nums.begin(),nums.end());

        //2. 利用双指针解决问题
        int n=nums.size();
        for(int i=0;i<n;)//固定数
        {
            if(nums[i]>0) break;//小优化
            //两数之和
            int left =i+1,right=n-1,target=-nums[i];
            while(left<right)
            {
                int sum=nums[left]+nums[right];
                if(sum>target) right--;
                else if(sum<target) left++;
                else //不要停 要找完
                {
                    ret.push_back({nums[i],nums[left],nums[right]});
                    left++,right--;
                    //去重操作 left和right
                    while(left<right && nums[left]==nums[left-1]) left++;
                    while(left<right && nums[right]==nums[right+1]) right--;
                }
            }
            //去重 i
            i++;
            while(i<n && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
};

class Solution
{
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) 
{
    vector<vector<int>> ret;
    // 1. 排序
    sort(nums.begin(), nums.end());
    // 2. 利⽤双指针解决问题
    int n = nums.size();
    for(int i = 0; i < n; ) // 固定数 a
    {
        // 利⽤ 三数之和
        for(int j = i + 1; j < n; ) // 固定数 b
        {
            // 双指针
            int left = j + 1, right = n - 1;
            long long aim = (long long)target - nums[i] - nums[j];
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum < aim) left++;
                else if(sum > aim) right--;
                else
                {
                    ret.push_back({nums[i], nums[j], nums[left++], 
                    nums[right--]});
                    // 去重⼀
                    while(left < right && nums[left] == nums[left - 1]) 
                    left++;
                    while(left < right && nums[right] == nums[right + 1]) 
                    right--;
                }
            }
            // 去重⼆
            j++;
            while(j < n && nums[j] == nums[j - 1]) j++;
        }
        // 去重三
        i++;
        while(i < n && nums[i] == nums[i - 1]) i++;
    }
    return ret;
    }
};


